package LeetcodeTrain;

import javafx.util.Pair;
import org.omg.CORBA.INTERNAL;
import org.omg.PortableInterceptor.INACTIVE;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author Hongliang Zhu
 * @create 2021-08-01 9:39
 */
public class leetcode1337_kWeakestRows {

    public int[] kWeakestRows(int[][] mat, int k) {
        Map<Integer, Integer> map = new TreeMap<>();

        for (int i = 0; i < mat.length; i++) {
            map.put(i, cal(mat[i]));
        }

        //2. 现将map转换为list，然后通过Lambda表达式进行升序排序
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, Comparator.comparing(Map.Entry::getValue));


        int[] res = new int[k];
        int p = 0;
        for (Map.Entry<Integer, Integer>  entry: list){
            if(p < k){
                res[p++] = entry.getKey();
            }else {
                break;
            }
        }
        return res;
    }

    public int[] kWeakestRows_Using_heapSort(int[][] mat, int k) {

        // 大根堆
        PriorityQueue<Pair<Integer, Integer>> p = new PriorityQueue<>((x, y) ->{
            if (!x.getValue().equals(y.getValue())){
                return y.getValue()-x.getValue();
            }else {
                return y.getKey() - x.getKey();
            }
        });
        for (int i = 0; i < mat.length; i++) {
            Pair<Integer, Integer> pair = new Pair<>(i, cal(mat[i]));
            if(p.size() < k){
                p.add(pair);
            }else {
                if(p.peek().getValue() > pair.getValue()){
                    p.poll();
                    p.add(pair);
                }

            }
        }


        int[] res = new int[k];
        int i = k-1;
        while(!p.isEmpty()){

            res[i--] = p.poll().getKey();
        }

        return res;


    }





    private int cal(int[] arr){
        Integer[] a = Arrays.stream(arr).boxed().toArray(Integer[]::new);
//        int res = 0;
        List<Integer> collect = Stream.of(a).collect(Collectors.toList());
        int sum = collect.stream().mapToInt(x -> x).sum();
        return sum;
    }

    /**
     * 二分查找最后一个1所在的位置
     * @param arr
     * @return
     */
    private int cal_in_binary(int[] arr){

        int l = 0;
        int r = arr.length-1;

        while (l < r){
            int m = (l + r + 1) >> 1;
            if( arr[m] == 1){
                l = m+1;
            }else {
                r = m-1;
            }
        }

        int pos = arr[r] == 1? r + 1: r;
        return pos;


    }

    public static void main(String[] args) {
        leetcode1337_kWeakestRows solution = new leetcode1337_kWeakestRows();

        int[][] mat ={{1,0,0,0},{1,1,1,1},{1,0,0,0},{1,0,0,0}};


        for (int i = 0; i < mat.length; i++){
            System.out.println(solution.cal_in_binary(mat[i]));
        }




//        int[] ints = solution.kWeakestRows(mat, 2);
//        int[] ints = solution.kWeakestRows_Using_heapSort(mat, 2);
//        for (int i = 0; i < ints.length; i++) {
//            System.out.println(ints[i]);
//        }
    }
}
